package com.leetcode.algorithm.y22.m06;

import java.util.Arrays;

/**
 * 1175. 质数排列
 * 
 * https://leetcode.cn/problems/prime-arrangements/
 * 
 * @author jie.deng
 *
 */
class Question1175Solution01 {

	public int numPrimeArrangements(int n) {
		int MOD = 1000000007;
		// 求1-n质数的个数
		int cnt = 0;
		boolean[] dp = new boolean[n + 1];
		Arrays.fill(dp, true);
		dp[0] = false;
		dp[1] = false;
		for (int i = 2; i < dp.length; i++) {
			if (!dp[i]) {
				continue;
			}
			cnt += 1;
			int idx = i + i;
			while (idx < dp.length) {
				dp[idx] = false;
				idx += i;
			}
		}

		long mul1 = factorial(cnt, MOD);
		long mul2 = factorial(n - cnt, MOD);
		return (int) (mul1 * mul2 % MOD);
	}

	private long factorial(int n, int MOD) {
		long mul = 1;
		while (n > 1) {
			mul *= n;
			mul %= MOD;
			n--;
		}
		return mul;
	}

}